    Baraj ziua 1 (Selectie lot IOI, Cluj, aprilie 1996)
    Problema 2 (Joc cu obiecte)

  Fie un sir de k c[sute pe care se afl[ amplasate 2*n, (k2*n) piese de dou[ 
culori (jum[tate rosii si jum[tate albastre), astfel nct s[ fie ndeplinite 
conditile: 
   1) In fiecare c[sut[ exist[ cel mult o pies[.
   2) Parcurgnd sirul c[sutelor de la stnga spre dreapta (sau invers), 
culorile pieselor vor alterna.
   3) Cea mai din stnga pies[ are culoarea rosie.
  Dou[ persoane A si B particip[ la urm[torul joc: Alternativ, cei doi pot muta
una din piesele lor (A poate muta doar piese rosii, iar B poate muta doar 
piese albastre) spre stnga sau spre dreapta, f[r[ a putea s[ri peste alte piese. 
Cel care nu mai poate muta, pierde. Initial mut[ A. 
Se cere:
   a) S[ se determine dac[ juc[torul A are strategie sigur[ de cstig;
   b) In caz afirmativ s[ se determine prima mutare pe care o va efectua 
juc[torul A. Se va afisa a cta pies[ rosie a fost mutat[, cu cte pozitii, 
si n ce sens.
Restrictii:
Numele fisierului de intrare se citeste de la tastatur[.
Fisierul de intrare are urm[toarea structur[:
 - pe prima linie: num[rul pieselor de o culoare (n);
 - pe a doua linie: un sir de caractere, avnd elementele n multimea {0,a,r} 
unde:
r = c[sut[ ocupat[ de piesa rosie;
a = c[sut[ ocupat[ de piesa albastr[;
0 = c[sut[ neocupat[. 
Num[rul c[sutelor este mai mic sau egal cu 1000.
Iesirea se face pe ecran.
Exemplu:
Pentru fisierul de intrare:
1
0000r0000000a0
programul va trebui s[ afiseze:
Juc[torul A are strategie sigur[ de castig.
A mut[ cu 7 pozitii spre dreapta piesa 1.

Not[: Timp maxim de executare pentru fiecare test: 1 secund[.
           Punctaj maxim: 100 puncte.
==============================
                Testele date n baraj:
Test 1:
1
ra
==========
Test 2:
2
r0ara
==================
Test 3:
3
r0000a00r0000a0r0000a0000
===================
Test 4:
4
000r0000000000000000000000000000000000000000000000000000000000000000a0
0r000000000000000000000000000000000000000000000000000000000000000a0000
r000000000000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000ara
=========================
Test 5:
5
00r0000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000ar00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ar00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ar00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ar00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000a
=======================
Test 6:
9
r000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000ar0000000ar0000000000000000000000000000000ar000000000000000000000000000000000000000000000000000000000000000000000000ar000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ar000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ar0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ar00000000000000000000ar0a
======================
Solutia 1: (Mihai Badoiu)
{$A+,B-,D-,E+,F-,G+,I-,L-,N+,O-,P-,Q-,R-,S-,T-,V+,X+,Y-}
{$M 65520,0,655360}
const
                max=10000;
var
                n:integer;
                v:array[1..max] of integer;
                virf:integer;

procedure load;
var
                f:text;
                nume:string;
                ch:char;
                stare,poz:integer;
begin
                write('nume fisier = ');
                readln(nume);
                assign(f,nume);
                reset(f);
                readln(f,n);
                           stare:=0;
                poz:=0;
                virf:=0;
                while not eoln(f) do
                begin
                                         read(f,ch);
                                         case ch of
                                                                           '0':if stare=1 then
                                                                                                                                                                                                                                       inc(poz);
                                                                           'r':stare:=1;
                                                                           'a':begin
                                                                                                                                                                          inc(virf);
                                                                                                                                                                          v[virf]:=poz;
                                                                                                                                                                          poz:=0;
                                                                                                                                                                          stare:=0;
                                                                                                                                                                          end;
                                                                           end;
                                         end;
                close(f);
end;

procedure calcul;
var
                k:integer;
                p,i,t,k2:integer;
begin
                k:=0;
                for i:=1 to virf do
                                         k:=k xor v[i];
                if k<>0 then
                begin
                                         writeln('Jucatorul A are strategie sigura de castig.');
                                         t:=1;
                                         k2:=k;
                                         while (k2<>0) do
                                         begin
                                                                           t:=t shl 1;
                                                                           k2:=k2 shr 1;
                                                                           end;
                                         for i:=1 to virf do
                                         begin
                                                                           t:=v[i] mod t;
                                                                           p:=0;
                                                                           while k<>0 do
                                                                           begin
                                                                                                                      k:=k xor t;
                                                                                                                      dec(t);
                                                                                                                      inc(p);
                                                                                                                      k:=k xor t;
                                                                                                                      end;
                                                                                                            writeln('A muta cu ',p,' pozitii spre dreapta.(piesa ',i,')');
                                                                           exit;
                                                                           end;
                                         end
                else
                                         writeln('Jucatorul A nu are strategie sigura de castig.'#13#10,
                                         'Daca jucatorul B se pricepa la acest joc atunci jucatorul A nu are',
                                         ' nici o sansa!!!');
end;

begin
                load;
                calcul;
end.
=================================
Solutia 2 (Catalin Francu):
program JocNim;
{$B- I- R- S-}
const NMax=500;
type Board=array[1..NMax] of Integer;

var N,X:Integer;
    B:Board;

procedure ReadData;
var i:Integer;
    S:String;
    C:Char;
begin
  Write('Numele fisierului de intrare: ');ReadLn(S);
  Assign(Input,S);Reset(Input);
  ReadLn(N);
  X:=0;
  for i:=1 to N do
    begin
      repeat Read(C) until C='r';
      B[i]:=-1;
      repeat Read(C);
             Inc(B[i]);
      until C='a';
      X:=X xor B[i];
    end;
  Close(Input);
end;

procedure FoundIt(i,j:Integer);
begin
  WriteLn('A muta piesa a ',i,'-a cu ',B[i]-j,' pozitii spre dreapta');
end;

procedure FindIt;
var i,j,X1,X2:Integer;
begin
  for i:=1 to N do
    begin
      X1:=X xor B[i]; { ca si cum le-as fi luat pe toate }
      for j:= 0 to B[i]-1 do
        begin
          X2:=X1 xor j;
          if X2=0 then FoundIt(i,j);
        end;
    end;
end;

begin
  ReadData;
  if X=0
    then WriteLn('Jucatorul A nu are strategie sigura de castig.')
    else begin
           WriteLn('Jucatorul A are strategie sigura de castig.');
           FindIt;
         end;
end.
======================================
Solutia 3 (Ovidiu Ghiorghioiu):
uses crt;
const kmax=1000;
type what=record
                p,n:integer
end;
var s:array[1..kmax] of char;
    d:array[1..kmax] of integer;
    o:array[1..kmax] of boolean;
    a:array[0..kmax,boolean] of boolean;
    b:array[0..kmax,boolean] of what;
    i,n,l,p,q:integer;
    j,k,m:boolean;
    nf:string;
    f:text;
procedure citeste;
begin
     write('Numele fis. de intrare: ');readln(nf);
     assign(f,nf);
     reset(f);
     readln(f,n);
     l:=0;
     while not seekeoln(f) do begin
           inc(l);
           read(f,s[l]);
     end;
     close(f);
end;
procedure rezolva;
begin
     j:=false;   {=Trebuie sa gasesc ceva}
     k:=false;   {=Trebuie sa gasesc "A"}
     p:=0;
     q:=0;
     for i:=1 to l do
         if (upcase(s[i])='A') or (upcase(s[i])='R') then begin
            m:=upcase(s[i])='A';
            if j then begin
               if m<>k then begin
                  writeln('Fis. de intrare nu este corect!');
                  halt
               end;
               inc(q);
               d[q]:=i-p-1;
               o[q]:=not k;
            end else p:=i;
            j:=not j;
            k:=not m
         end;
    if j or (q<>n) then begin
         writeln('Fis. de intrare nu este corect!');
         halt
    end;
    fillchar(a,sizeof(a),false);
    a[0,false]:=true;
    b[0,false].p:=0;
    for i:=1 to n do
        for j:=false to true do
            if a[i-1,not j] and (d[i]>0) then begin
               a[i,j]:=true;
               b[i,j].p:=i;
               b[i,j].n:=d[i];
            end else
            if a[i-1,j] and (d[i]<>1) then begin
               a[i,j]:=true;
               if d[i]>0 then begin
                  b[i,j].p:=i;
                  b[i,j].n:=d[i]-1
               end else b[i,j]:=b[i-1,j]
            end;
end;
procedure scrie;
begin
     if a[n,true] then begin
        writeln('Jucatorul A are strategie sigura de castig');
        write('A muta piesa ',b[n,true].p,' cu ',b[n,true].n,' pozitii la ');
        if o[b[n,true].p] then writeln('stanga') else writeln('dreapta')
     end else writeln('Jucatorul A nu are strategie sigura de castig');
end;
begin
     citeste;
     rezolva;
     scrie;
end.
=========================
